import java.util.TreeSet;
import java.util.HashSet;
import java.util.TreeMap;
import java.util.ArrayList;

/**
 *
 * @author Zuzana Krejcova
 */
public abstract class EliminaceEpsilon
{
    /**
     * Transformace gramatiky na ekvivalentni gramatiku bez epsilon pravidel
     * @param g Gramatika k transformaci
     * @return Gramatika jiz transformovana, bez epsilon pravidel
     */
    public static Object[] transformuj(Gramatika g)
    {
        TreeSet<String> netermy = new TreeSet();
        TreeSet<String> pomocneNetermy = new TreeSet();
        String novyKoren = new String(g.koren);
        TreeMap<String,HashSet<ArrayList<String>>> novaPravidla = new TreeMap();

        do //konstrukce mnoziny N_epsilon
        {
            pomocneNetermy.addAll(netermy);
            for (String neterm : g.pravidla.keySet())
            {
                if (jdeDerivovatNaEpsilon(g.pravidla.get(neterm), pomocneNetermy)) netermy.add(neterm);
            }
        } while (!pomocneNetermy.containsAll(netermy));

        //pridavani pravidel
        for (String neterm : g.pravidla.keySet())
        {
            novaPravidla.put(neterm, new HashSet()); //vloz vsechny netermy z puvodnich pravidel a prazdne mnoziny pravych stran
            for (ArrayList<String> pravaStrana : g.pravidla.get(neterm))
            {
                if (obsahujeEpsilon(pravaStrana, netermy)) //pokud prava strana obsahuje netermy ze zkonstruovane mnoziny nebo epsilon
                {
                    HashSet<ArrayList<String>> praveStrany;
                    praveStrany = nahradPravidlo(pravaStrana, netermy, g.terminaly); //zkonstruuj mnozinu novych potrebnych pravidel
                    if (praveStrany != null) novaPravidla.get(neterm).addAll(praveStrany); //a pokud neni prazdna, pridej je k pravidlum pro dany neterm
                } else //jinak tam to pravidlo proste pridej
                {
                    novaPravidla.get(neterm).add(pravaStrana);
                }
            }
            if (novaPravidla.get(neterm).isEmpty()) novaPravidla.remove(neterm);
        }

        TreeSet<String> noveNetermy = new TreeSet(g.neterminaly);
        String koren = novyKoren;

        if (netermy.contains(novyKoren))
        {
            String nahradniKoren;
            do
            {
                nahradniKoren=novyKoren+"'";
            } while (neterminalPouzit(g.neterminaly,nahradniKoren));
            HashSet<ArrayList<String>> praveStrany = new HashSet();
            ArrayList<String> eps = new ArrayList();
            ArrayList<String> kor = new ArrayList();
            eps.add("\u03B5");
            kor.add(novyKoren);
            praveStrany.add(eps);
            praveStrany.add(kor);

            novaPravidla.put(nahradniKoren, praveStrany);
            noveNetermy.add(nahradniKoren);
            koren = nahradniKoren;
        }

        Object[] ret = new Object[2];
        Gramatika novaGramatika = new Gramatika(noveNetermy, new TreeSet(g.terminaly), koren, novaPravidla);
        novaGramatika.bezEpsilon = true;
        ret[0] = novaGramatika;
        String retS = "Množina N(\u03B5) = {";
        for (String neterm : pomocneNetermy)
        {
            retS += neterm+",";
        }
        retS = retS.substring(0, retS.length()-1);
        retS += "}\n\n";
        ret[1] = retS;
        return ret;
    }

    /**
     * Zjisti, zda lze nejakou z dane mnoziny pravych stran pravidla prepsat na
     * epsilon (pomoci mnoziny uz prohledanych symbolu)
     * @param praveStrany
     * @param dosazeneSymboly
     * @return true pokud lze prepsat na epsilon
     */
    private static boolean jdeDerivovatNaEpsilon(HashSet<ArrayList<String>> praveStrany, TreeSet<String> dosazeneSymboly)
    {
        for (ArrayList<String> jednaPravaStrana : praveStrany)
        {
            if (vsechnyPrepsatelneNaEpsilon(jednaPravaStrana, dosazeneSymboly)) return true;
        }
        return false;
    }

    private static boolean vsechnyPrepsatelneNaEpsilon(ArrayList<String> jednaPravaStrana, TreeSet<String> dosazeneSymboly)
    {
        for (int i=0; i < jednaPravaStrana.size();i++)
        {
            if ((!jednaPravaStrana.get(i).equals("\u03B5"))
               &&(!dosazeneSymboly.contains(jednaPravaStrana.get(i)))) return false;
        }
        return true;
    }

    /**
     * Zjistuje, zda se v konkretni prave strane objevuje epsilon, nebo neterminal
     * na epsilon prepsatelny
     * @param pravaStrana
     * @param dosazeneSymboly
     * @return true pokud obsahuje epsilon nebo neterminal prepsatelny na epsilon
     */
    private static boolean obsahujeEpsilon(ArrayList<String> pravaStrana, TreeSet<String> dosazeneSymboly)
    {
        for (int i=0; i < pravaStrana.size();i++)
        {
            if ((pravaStrana.get(i).equals("\u03B5"))
               ||(dosazeneSymboly.contains(pravaStrana.get(i)))) return true;
        }
        return false;
    }

    private static HashSet<ArrayList<String>> nahradPravidlo(ArrayList<String> pravaStrana, TreeSet<String> netermy, TreeSet<String> termy)
    {
        /*
         * bitarray delky podle poctu netermu, ktere se daji prepsat na epsilon, vsechna pole inicializovat na 0
         * forcyklus s poctem tech netermu na druhou pruchodu
         * cislo delit 2 a vepisovat zbytek do bitarray
         *
         * n-ty prvek bitarray odpovida n-temu vyskytu problematickeho netermu
         * pokud je na poli 0, neterm vypustime
         * pokud je tam 1, prvek tam nechame
         *
         * duplicitni pravidla se diky hashsetu nepridaji dvakrat
         *
         * nutno kontrolovat, jestli vysledny arraylist neni prazdny
         *  - staci vedet, jestli prvni String neni "" (prazdny)
         * prazdne arraylisty nepridavat
         *
         * pokud je hashset na konci prazdny, vracim null
         */
        HashSet<ArrayList<String>> kPridani = new HashSet();
        byte[] bitArray;
        byte pocetPrepsatelnychNetermu =0;
        short pocetVariaci;
        if (pravaStrana.get(0).equals("\u03B5")) return null;
        for (int i = 0; i < pravaStrana.size(); i++)
        {
            if (netermy.contains(pravaStrana.get(i))) pocetPrepsatelnychNetermu++;
        }
        bitArray = new byte[pocetPrepsatelnychNetermu];
        for (int i = 0; i < pocetPrepsatelnychNetermu; i++)
        {
            bitArray[i]=0;
        }
        pocetVariaci = (short)Math.pow(2.0, (double)pocetPrepsatelnychNetermu);
        for(short i = 0; i < pocetVariaci; i++)
        {
            short podil = i;
            short index = 0;
            do
            {
                bitArray[index]=(byte)(podil%2);
                podil=(byte)(podil/2);
                index++;
            } while (podil != 0);
            //variace netermu
            ArrayList<String> novaPravaStrana = new ArrayList();
            index = 0;
            for (short j = 0; j < pravaStrana.size(); j++)
            {
                if (termy.contains(pravaStrana.get(j)))
                {
                    novaPravaStrana.add(pravaStrana.get(j));
                } else
                {
                    if (netermy.contains(pravaStrana.get(j)))
                    {
                        if (bitArray[index] == 1) novaPravaStrana.add(pravaStrana.get(j));
                        index++;
                    } else
                    {
                        novaPravaStrana.add(pravaStrana.get(j));
                    }
                }
            }
            if (!novaPravaStrana.isEmpty()) kPridani.add(novaPravaStrana);
        }
        if (kPridani.isEmpty()) return null;
        return kPridani;
    }

    private static boolean neterminalPouzit(TreeSet<String> netermy, String novyKoren)
    {
        for (String neterm : netermy)
        {
            if (neterm.equals(novyKoren)) return true;
        }
        return false;
    }
}
